package seqList.DoubleLink;

public class DoubleLinkedList {
    // 当前链表中有效的元素个数
    private int size;
    // 头节点
    private Node head;
    // 尾节点
    private Node tail;

    public void addFirst(int val) {
        Node node = new Node(null,val,head);
        if (head == null) {
            // 当前链表为空
            tail = node;
        }else {
            // 链表不为空
            head.prev = node;
        }
        // 无论链表是否为空，最后node节点都是最新的头节点
        head = node;
        size ++;
    }

    public void addLast(int val) {
        Node node = new Node(tail,val,null);
        if (tail == null) {
            head = node;
        }else {
            tail.next = node;
        }
        tail = node;
        size ++;
    }

    /**
     * 在链表的中间位置插入元素
     * @param index
     * @param val
     */
    public void addIndex(int index,int val) {
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }else if (index == 0) addFirst(val);
        else if (index == size) addLast(val);
        else {
            // 在中间位置插入，找到index的前驱节点
            // 找节点 -> 写成方法
            Node prev = node(index - 1);
            // 连接四根线
            Node newNode = new Node(prev,val,prev.next);
            prev.next.prev = newNode;
            prev.next = newNode;
            size ++;
        }
    }

    public int get(int index) {
        // index合法性
        if(rangeIndex(index)) {
            return node(index).val;
        }else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    public boolean contains(int val) {
        for (Node x = head;x != null;x = x.next) {
            if (x.val == val) {
                return true;
            }
        }
        return false;
    }

    /**
     * 根据index修改元素值
     * @param index
     * @param newVal
     * @return 修改前的值
     */
    public int set(int index,int newVal) {
        if (rangeIndex(index)) {
            Node node = node(index);
            int oldVal = node.val;
            node.val = newVal;
            return oldVal;
        }else {
            System.err.println("set index illegal!");
            return -1;
        }
    }

    private boolean rangeIndex(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        String ret = "";
        Node node = head;
        while (node != null) {
            ret += node.val + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    public void removeIndex(int index) {
        if (rangeIndex(index)) {
            Node node = node(index);
            unlink(node);
        }else {
            System.err.println("remove index illegal!");
        }
    }

    public void removeValueOnce(int val) {
        // 找到待删除节点
        for (Node x = head;x != null;x = x.next) {
            if (x.val == val) {
                unlink(x);
                break;
            }
        }
    }

    public void removeValueAll(int val) {
        for (Node x = head;x != null;) {
            if (x.val == val) {
                // x是待删除节点
                // next是下一个要判断的节点
                Node next = x.next;
                // 删除之后，x.next = x.prev = null
                unlink(x);
                x = next;
            }else {
                // 继续向后走
                x = x.next;
            }
        }
    }

    /**
     * 在双向链表中删除指定的node节点
     * @param node
     */
    private void unlink(Node node) {
        // 分治思想
        Node prev = node.prev;
        Node next = node.next;
        // 先处理前驱节点
        if (prev == null) {
            // 此时是个头节点
            head = next;
        }else {
            // 有前驱
            prev.next = next;
            node.prev = null;
        }
        // 此时接着处理后半边的情况
        if (next == null) {
            // 此时node是个尾节点
            tail = prev;
        }else {
            next.prev = prev;
            node.next = null;
        }
        size --;
    }

    /**
     * 找到index索引对应的节点
     * @param index
     * @return index对应的节点Node
     */
    private Node node(int index) {
        Node ret = null;
        // index < size / 2(从头找)
        if (index < (size >> 1)) {
            ret = head;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
        }else {
            // 此时从后向前遍历
            ret = tail;
            for (int i = size - 1;i > index;i--) {
                ret = ret.prev;
            }
        }
        return ret;
    }
}

/**
 * 双链表的节点类
 */
class Node {
    // 指向前驱节点
    Node prev;
    // 保存具体值
    int val;
    // 指向后继节点
    Node next;

    public Node(int val) {
        this.val = val;
    }

    public Node(Node prev, int val, Node next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}